/**
 * 
 */
package tree;

/**
 * @author Michael
 * 
 * Given a binary tree, populate the next right pointers in each node.
 * You may assume that it is a full binary tree.
 * Each node other than the leaves has two children.
 */
public class AddRightSiblingPointersToNodes {

	public static class NodeWithRightSiblingPointer<T extends Comparable<? super T>> extends Node<T> {

		
		public NodeWithRightSiblingPointer<T> rightSibling = null;
		public NodeWithRightSiblingPointer<T> right = null;
		public NodeWithRightSiblingPointer<T> left = null;
		public NodeWithRightSiblingPointer(T value) {
			super(value);
		}
	}

	public static <T extends Comparable<? super T>> void populateFullBT(NodeWithRightSiblingPointer<T> root) {
		if (null == root)
			return;
		
		if (root.left != null) {
			root.left.rightSibling = root.right;
		}
		if (root.right != null && root.rightSibling != null) {
			root.right.rightSibling = root.rightSibling.left;
		}
		populateFullBT(root.left);
		populateFullBT(root.right);
	}
	
	public static void populateBT(NodeWithRightSiblingPointer root) {
		
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	}

	/**
	 * 
	 */
	public AddRightSiblingPointersToNodes() {
		// TODO Auto-generated constructor stub
	}

}